简介
从名字可以看出，这篇论文是关于相似搜索，并通过最优稀疏提升(Optimal Sparse Lifting)，加快相似搜索的速度和精度。这篇论文来自nips2018，是在之前介绍过的A neural algorithm for a fundamental computing problem的基础上更进一步。我们知道，之前的算法通常将输入映射到更低维的空间，来减少计算复杂度并加快相似搜索的速度。果蝇算法却通过稀疏二值随机矩阵将输入映射到更高维的输出空间，同时保留输入数据之间的相似性。果蝇算法的映射矩阵是以概率$p$随机生成的，但我们知道，神经连接的过程是动态变化的，会随着时间推进而逐渐优化（我个人认为是这样）。所以这篇论文提出了最优提升算子。该论文提出的方法有关键的两步：第一步，根据提供的输入样本(一小部分)，计算它们的最优稀疏提升，也就是将输入样本映射到更高维的稀疏空间，并尽量保留数据之间的相似性,最优稀疏提升即是输入样本在更高维空间的稀疏二值向量表征；第二步是寻找最优提升算子，其是将输入数据映射到最优稀疏提升的最佳稀疏二值矩阵。这两步都可以看作优化问题，可以使用 Frank-Wolfe algorithm来高效求解。前言和相关工作在此略过不提，感兴趣可以看看A neural algorithm for a fundamental computing problem。
论文地址
Models
The optimal sparse lifting framework
作者关心的问题是在输出空间维度大于或者远远大于给定的输入空间维度的情况下，求得给定的输入样本的稀疏二值输出向量。作者希望输入空间中数据之间的相似性，当输入数据转变为输出空间中的新向量之后，能够尽量保留它们之间的相似性。更进一步，如果能够得到小部分输入数据的最优输出向量，作者希望能以一种近似、计算上更经济的方法，获得其他输入数据的最优输出向量，也就是求解最优提升算子。
作者们将这两个问题建模为一个统一最优稀疏提升框架。令$X \in R^{d \times m}$是在$d$维空间中的输入样本的矩阵。希望最小化的目标如下所示：
$W \in R^{d’ \times d}$,$Y \in R^{d’ \times m}$，并且$W$和$Y$被要求是稀疏的。上式的第一项旨在确保$Y \approx WX$。第二项希望尽可能的保留输入数据在输出空间中原来的相似性关系。上式中$\alpha >0$ 是一个平衡参数。
输出空间是$d’$维的，并且$d’ \gg d$。因此输出$Y$被称为是输入$X$的稀疏提升，矩阵$W$被称为是稀疏提升算子。
除了对$W$的稀疏约束外，作者还期望$W$是二值的，并且每一行恰好有$c$个1。如果将二值约束放宽到单位区间(unit interval)约束，$W$就应该逐分量(component-wise)满足(ps:这个公式我没看懂什么意思):
同样$Y$也被加上同样的约束:
希望$Y$每一列恰恰有$k$个1。但如果最优先的目的是使用训练集获得一个较好的$W$，那么对$Y$加上更少的约束比较好。
在公式一中的问题，可以通过交替最小化来解决。固定住$W$,求解$Y$；然后固定住$Y$，求解$W$；重复以上过程。有一种简化方法，在实践中表现的，使用伪范数$\ell_p$(0< $p$ < 1)促进稀疏性和二值化(ps:虽然不知道伪范数是什么，但可以看出它可以确保输出空间中新向量保留原来的相似性关系)。最佳稀疏提升$Y_*$的求解如下:
最佳稀疏算子$W_*$的求解如下：
两个公式的第二项都是惩罚项，目的是令其稀疏化。值得一提的是，这里的”最优”，实际上是近似最优解。
有了最优提升算子$W_*$，输入向量$x$的最优稀疏提升&y&就可以被计算出来,$y = (y_1,…,y_{d’}) \in {\{0,1\}}^{d’}$:
这一步也就是果蝇算法中的赢者通吃策略。
Algorithm
有许多优化方法可以用来求解公式(4)和公式(5)表示的最小化问题。该论文采用了Frank-Wolfe algorithm，这是一种用于约束优化的迭代一阶优化方法。详情可以看看这篇博文。在每次迭代中，该优化算法将目标函数作线性近似，通过求解线性规划求得可行下降方向,并沿该方向在可行域内作一维搜索。基于Frank-Wolfe algorithm，一种用来对公式(4)最小化的简单迭代解决方法如Algorithm 1所示：
如果不考虑line 6 平衡参数$\gamma$的增加(随着每次迭代，单调递增,可令输出矩阵$Y$更稀疏和二值化)，该算法就是一个标准的Frank-Wolfe algorithm。在每次迭代中，最大的计算开销来自于line 4 的求解线性规划过程。尽管这里线性规划可能涉及上百万甚至更多的变量，也可以使用现代优化技术高效求解。公式(5)可用同样的算法求解。
Optimal lifting vs. random lifting
果蝇算法使用随机生成的数据转化矩阵$W$将输入$X$映射到更高维的空间，再紧接一个稀疏化和二值化过程。和LSH算法一样，有理论证明，输出向量保留了输入向量之间的$\ell_p$距离（也就是相似性关系）。但是考虑到其后有一个稀疏化和二值化过程，就没有强力的理论可以保证这一点。
尽管同样是受果蝇嗅觉神经回路这一生物证据的启发，该论文以完全不同的视角出发，研究扩展到高维空间的相似搜索问题。这里有两个关键的novelties。该论文将果蝇算法的过程形式化定义为稀疏提升。输入向量被提升为更高维空间中的稀疏二值向量，并且特征值由它们的高能量集中位置代替(最大的$k$个数)，并进一步以稀疏二进制编码表征。
一个更有意义的novelty体现在将输入向量映射到更高维输出向量的原则中。果蝇算法使用随机生成的矩阵$W$，可以被认为是随机提升方法。这样能量集中位置的产生就会带有随机性。与此同时，PNs到KCs的生物连接机制尚不完全清楚，最近来自动物大脑的电子显微镜图像表明连接并不是随机的。形成对照的是，该论文将映射建模为优化问题，实际上减少了随机性。
思考
我认为这篇文章的亮点在于，使用伪范数评估映射矩阵的表现，并将其转换一个优化问题，移除了连接的随机性，更加符合生物学证据。另一个就是名字取得很好。